| 翻訳と辞書 |
| Computable topology ： ウィキペディア英語版 |
Computable topology
Computable topology is a discipline in mathematics that studies the topological and algebraic structure of computation. Computable topology includes algorithmic topology and therefore encompasses computer science. It is not to be confused with ''computational topology'', which is equivalent to the topology of λ-calculus. Within computer science computational forms can be reduced to λ-calculus's functional based mathematics. As shown by Alan Turing and Alonzo Church, the λ-calculus is strong enough to describe all mechanically computable functions (see Church–Turing thesis).〔Church 1934:90 footnote in Davis 1952〕〔Turing 1936–7 in Davis 1952:149〕〔Barendregt, H.P., The Lambda Calculus Syntax and Semantics. North-Holland Publishing Company. 1981〕 Lambda-calculus is then a foundational mathematics easily made into a principal programming language from which other languages can be built. For this reason when considering the topology of computation it is suitable to focus on the topology of λ-calculus. Functional programming, e.g. type free lambda calculus, originated as a theoretical foundation of mathematics. The premise relies on functional computability, where objects and functions are of the same type. The topology of λ-calculus is the Scott topology, and when restricted to continuous functions the type free λ-calculus amounts to a topological space reliant on the tree topology. Both the Scott and Tree topologies exhibit continuity with respect to the binary operators of application ( f ''applied to'' a = fa ) and abstraction ((λx.t(x))a = t(a)) with a modular equivalence relation based on a congruency. The algebraic structure of computation may also be considered as equivalent to the algebraic structure of λ-calculus, meaning the λ-algebra. The λ-algebra is found to be an extension of the combinatory algebra, with an element introduced to accommodate abstraction.
A primary concern of algorithmic topology, as its name suggests, is to develop efficient algorithms for solving topological problems, or using topological methods to solve algorithmic problems from other fields.
==Computational topology from λ-calculus topology==
Type free λ-calculus treats functions as rules and does not differentiate functions and the objects which they are applied to, meaning λ-calculus is type free. A by-product of type free λ-calculus is an effective computability equivalent to general recursion and Turing machines.〔Barendregt, H.P., The Lambda Calculus Syntax and Semantics. North-Holland Publishing Company. 1981.〕 The set of λ-terms can be considered a functional topology in which a function space can be embedded, meaning λ mappings within the space X are such that λ:X → X.〔〔D. S. Scott. Models for the λ-calculus. Informally distributed, 1969. Notes, December 1969, Oxford Univ.〕 Introduced November 1969, Dana Scott's untyped set theoretic model constructed a proper topology for any λ-calculus model whose function space is limited to continuous functions.〔〔 The result of a Scott continuous λ-calculus topology is a function space built upon a programming semantic allowing fixed point combinatorics, such as the Y combinator, and data types.〔Gordon, M.J.C., The Denotational Description of Programming Languages. Springer Verlag, Berlin. 1979.〕〔Scott, D. S. and Strachey, C. Toward a Mathematical Semantics for Computer Languages, Proc. Symp. on Computers and Automata, Polytechnic Institute of Brooklyn, 21, pp. 19 46. 1971.〕 By 1971, λ-calculus was equipped to define any sequential computation and could be easily adapted to parallel computations.〔G. Berry, Sequential algorithms on concrete data structures, Theoretical Computer Science 20, 265 321 (1982).〕 The reducibility of all computations to λ-calculus allows these λ-topological properties to become adopted by all programming languages.〔
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Computable topology」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|